翻訳と辞書 Words near each other ・ Vertex configuration ・ Vertex cover ・ Vertex cycle cover ・ Vertex distance ・ Vertex enumeration problem ・ Vertex figure ・ Vertex function ・ Vertex Group ・ Vertex Inc ・ Vertex model ・ Vertex normal ・ Vertex of a representation ・ Vertex operator algebra ・ Vertex Pharmaceuticals ・ Vertex pipeline ・ Vertex separator ・ Vertex-transitive graph ・ VertexFX ・ Vertexguy ・ Vertexicola ・ Vertfee Takahara Nasu ・ Verthemex ・ Vertheuil ・ VertiBird ・ VERTIC ・ Vertic ・ Vertica ・ Vertica (butterfly) ・ Vertical ・ Vertical (1967 film) Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Vertex separator ： ウィキペディア英語版 Vertex separator In graph theory, a vertex subset $S\; \backslash subset\; V$ is a vertex separator (or vertex cut, separating set) for nonadjacent vertices $a$ and $b$ if the removal of $S$ from the graph separates $a$ and $b$ into distinct connected components. ==Examples== Consider a grid graph with ''r'' rows and ''c'' columns; the total number ''n'' of vertices is ''r *c''. For instance, in the illustration, ''r'' = 5, ''c'' = 8, and ''n'' = 40. If ''r'' is odd, there is a single central row, and otherwise there are two rows equally close to the center; similarly, if ''c'' is odd, there is a single central column, and otherwise there are two columns equally close to the center. Choosing ''S'' to be any of these central rows or columns, and removing ''S'' from the graph, partitions the graph into two smaller connected subgraphs ''A'' and ''B'', each of which has at most ''n''/2 vertices. If ''r'' ≤ ''c'' (as in the illustration), then choosing a central column will give a separator ''S'' with ''r'' ≤ √''n'' vertices, and similarly if ''c'' ≤ ''r'' then choosing a central row will give a separator with at most √''n'' vertices. Thus, every grid graph has a separator ''S'' of size at most √''n'', the removal of which partitions it into two connected components, each of size at most ''n''/2.〔. Instead of using a row or column of a grid graph, George partitions the graph into four pieces by using the union of a row and a column as a separator.〕 To give another class of examples, every free tree ''T'' has a separator ''S'' consisting of a single vertex, the removal of which partitions ''T'' into two or more connected components, each of size at most ''n''/2. More precisely, there is always exactly one or exactly two vertices, which amount to such a separator, depending on whether the tree is centered or bicentered. As opposed to these examples, not all vertex separators are ''balanced'', but that property is most useful for applications in computer science, such as the planar separator theorem. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Vertex separator」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.